package com.linyaonan.leetcode.medium._1448;


/**
 * 给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。
 *
 * 「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：root = [3,1,4,3,null,1,5]
 * 输出：4
 * 解释：图中蓝色节点为好节点。
 * 根节点 (3) 永远是个好节点。
 * 节点 4 -> (3,4) 是路径中的最大值。
 * 节点 5 -> (3,4,5) 是路径中的最大值。
 * 节点 3 -> (3,1,3) 是路径中的最大值。
 *
 * 二叉树中节点数目范围是 [1, 10^5] 。
 * 每个节点权值的范围是 [-10^4, 10^4] 。
 *
 * @author: Lin
 * @date: 2024/3/18
 */
public class CountGoodNodesInBinaryTree {

    int c = 0;

    public int goodNodes(TreeNode root) {
        c = 0;
        if (root == null) {
            return c;
        }

        dfs(root, root.val);

        return c;
    }

    /**
     * 当节点大于等于max值时认为有效
     * @param node
     * @param max
     */
    private void dfs(TreeNode node, int max) {
        if (node != null) {

            int cc = node.val;
            if (cc >= max) {
                c++;
                max = cc;
            }
            dfs(node.left, max);
            dfs(node.right, max);
        }
    }

}
